Truemper configurations are four types of graphs (namely thetas, wheels,prisms and pyramids) that play an important role in the proof of severaldecomposition theorems for hereditary graph classes. In this paper, we provetwo structure theorems: one for graphs with no thetas, wheels and prisms asinduced subgraphs, and one for graphs with no thetas, wheels and pyramids asinduced subgraphs. A consequence is a polynomial time recognition algorithmsfor these two classes. In Part II of this series we generalize these results tographs with no thetas and wheels as induced subgraphs, and in Parts III and IV,using the obtained structure, we solve several optimization problems for thesegraphs.
展开▼
